package algocasts;

import java.util.Stack;

public class P147_MaximalRectangle {
    private int largestRectangleInHistogram(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int max = 0, n = heights.length;
        Stack<Integer> stack = new Stack<>();
        for (int r = 0; r <= n; r++) {
            int h = r == n ? 0 : heights[r];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int idx = stack.pop();
                int l = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, heights[idx] * (r - l - 1));
            }
            stack.push(r);
        }
        return max;
    }

    // Time: O(m * n)  Space: O(n)
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0
                || matrix[0] == null || matrix[0].length == 0)
            return 0;
        int m = matrix.length, n = matrix[0].length;
        int[] heights = new int[n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            max = Math.max(max, largestRectangleInHistogram(heights));
        }
        return max;
    }
}
